package offer;

import java.util.ArrayList;

//栈的压入、弹出序列
public class T22 {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        int i=0;
        int j=0;
        while (i<pushA.length&&j<popA.length) {
             if (pushA[i]==popA[j]) {
                 i++;j++;
                   if (arrayList.size()!=0) {
                       while (arrayList.size()>0&&arrayList.get(arrayList.size()-1)==popA[j]) {
                           arrayList.remove(arrayList.size()-1);
                           j++;
                       }

                   }

             }else {
                 arrayList.add(pushA[i]);
                 i++;
             }
        }
        while (arrayList.size()>0&&arrayList.get(arrayList.size()-1)==popA[j]) {
            arrayList.remove(popA[j]);
            j++;
        }

        if (arrayList.size()==0) return true;
        return false;
    }
    public static void main ( String[] args) {

        System.out.println(new T22().IsPopOrder(
                new int[]{1,2,3,4,5},
                new int[]{4,5,3,2,1}
        ));
    }
}
